package arithmetic;

import java.util.LinkedList;
import java.util.Stack;

class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        listNode.next=listNode1;
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        reorderList(listNode);
    }
    public static void reorderList(ListNode head) {
        //第一遍遍历查看链表中的个数
        int count=0;
        ListNode cur=head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        //重新遍历放入栈中
        LinkedList<ListNode> stack1=new LinkedList<>();
        Stack<ListNode> stack2=new Stack<>();
        //重新遍历
        cur=head;
        for(int i=0;i<count/2;++i){
            //前半段入栈
            stack1.offer(cur);
            cur=cur.next;     
        }
        //后半段入栈
        while(cur!=null){
            stack2.push(cur);
            cur=cur.next;
        }
        stack1.pop();
        cur=head;
        //栈中取出
        while(stack1.size()!=0||!stack2.empty()){
            if(!stack2.empty()){
                cur.next=stack2.pop();
                cur=cur.next;
            }
            if(stack1.size()!=0){
                cur.next=stack1.pop();
                cur=cur.next;
            }
        }
        //最后解除循环
        cur.next=null;
    }
}